package top.minuy.structure.graph.path.dfs;

import top.minuy.structure.graph.representations.table.Graph;

import java.util.ArrayList;
import java.util.Collections;

/**
 * 单路径规划，深度优先遍历
 *
 * @author Minuy
 * @time 23:05
 * @date 2021/11/16
 */
public class SingleSourcePath {

    private Graph g;
    private int s;
    private boolean[] isVisited;

    private int[] pre;

    public SingleSourcePath(Graph g, int s) {
        this.g = g;

        // 验证源顶点的合法性
        g.validateVertex(s);
        this.s = s;

        // 开辟空间，初始化内容
        this.isVisited = new boolean[g.V()];
        this.pre = new int[g.V()];
        for (int i = 0; i < this.pre.length; i++) {
            this.pre[i] = -1;
        }

        // 从源结点开始对整个联通分量进行遍历
        // （因为求路径，不同联通分量之间肯定没有路径）
        dfs(s, s);  // 深度优先遍历
    }

    /**
     * 深度优先遍历
     *
     * @param v      遍历开始的顶点
     * @param parent v的上一个被遍历的顶点
     * @author Minuy
     * @date 2021/11/16 23:42
     */
    private void dfs(int v, int parent) {
        isVisited[v] = true;
        pre[v] = parent;  // 记录其上一个被遍历的顶点
        for (Integer w : g.adj(v)) {
            if (!isVisited[w]) {
                dfs(w, v); // 父顶点是现在被遍历到的v
            }
        }
    }

    /**
     * 查询源顶点是否联通到目标顶点
     *
     * @param t 目标顶点
     * @return boolean
     * @author Minuy
     * @date 2021/11/16 23:29
     */
    public boolean isConnectedTo(int t) {
        g.validateVertex(t);
        return isVisited[t]; // 如果被遍历到了，肯定联通
    }

    /**
     * 求到目标顶点的路径
     *
     * @param t 目标顶点
     * @return Iterable<Integer> 一个数组，可遍历，为路径上所经过的顶点
     * @author Minuy
     * @date 2021/11/16 23:32
     */
    public Iterable<Integer> path(int t) {
        g.validateVertex(t);

        ArrayList<Integer> p = new ArrayList<>();
        if (!isConnectedTo(t)) {
            // 如果不联通的，直接返回空路径列表
            return p;
        }

        int cur = t;
        while (cur != s) {
            p.add(cur);  // 记录路径
            cur = pre[cur];  // 找到它的父顶点
        }
        p.add(s); // 因为到s就出来了，所以记录一下

        // 给路径倒序一下
        Collections.reverse(p);
        return p;
    }

}
